# -*- coding: utf-8 -*-

"""剑指 Offer II 096. 字符串交织
给定三个字符串 s1、s2、s3，请判断 s3 能不能由 s1 和 s2 交织（交错） 组成。
两个字符串 s 和 t 交织 的定义与过程如下，其中每个字符串都会被分割成若干 非空 子字符串：
s = s1 + s2 + ... + sn
t = t1 + t2 + ... + tm
|n - m| <= 1
交织 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...
提示：a + b 意味着字符串 a 和 b 连接。

示例 1：
输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
输出：true

示例 2：
输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
输出：false

示例 3：
输入：s1 = "", s2 = "", s3 = ""
输出：true

提示：
0 <= s1.length, s2.length <= 100
0 <= s3.length <= 200
s1、s2、和 s3 都由小写英文字母组成"""


class Solution:
    """本题一开始容易陷入子序列矩阵的陷阱，找不出规律。
    后面看题解，s1前第 i 位与 s2前第 j 位 交织, 那么交织的s3末位 last=i+j+1(i+1+j+1-1)
    if s3[last] == s1[i]: f(i,j) = f(i-1, j)
    if s3[last] == s2[j]: f(i,j) = f(i, j-1)
    if s3[last] not in (s1[i], s2[j]): f(i, j) = false
    
    不过此题还是通过矩阵来解决，并且更容易理解
         d   b   b   c   a
    -|---|---|---|---|---|---|-
    a| s |   |   |   |   |   |
    -|---t---t---|---|---|---|-
    a| s | s |   |   |   |   |
    -|---|---|---|---|---|---|-
    b|   |   |   |   |   |   |
    -|---|---|---|---|---|---|-
    c|   |   |   |   |   | n |
    -|---|---|---|---|---m---|-
    c|   |   |   |   | y | p |
    -|---|---|---|---x---q---|-
    此题矩阵并不是严格的矩阵，格子和顶点都要占位置，交织就是以dbbca为隔板，往隔板中间插入aabcc，只不过插入顺序有讲究，
    反映到矩阵中就是行走路径，见左上角，通过插件 s 可以往两个方向移动：到达下一个插件 下边s，到达下一个隔板，右下顶点t；
                                    通过隔板 t 也可以往两个方向移动：到达下一个隔板 右边t，到达下一个插件，右下格子s
    那么此题要解决的就是有没有一条路径走到最后一个格子，或者最后一个顶点，经过的插件/隔板与s3一致
    假若最后到达的是格子 p，那么是否有路径走到 m 或者 n；如果最后到达的是顶点 q，那么有没有路径走到 x 或者 y？
    
    到达某个位置有没有有效路径的答案是一定的，且答案可以行走路径来推演，可以用动态规划来解决
    以f(i,j,x)表示答案(通过i，j，到达格子:=0/顶点:=1是否存在有效路径)
    那么：
    f(i,j) = f(i,j,0) || f(i,j,1)
    f(i,j,0) = (f(i-1, j, 1) || f(i-1, j, 0)) && s1[i] == s3[i+j+1]
    f(i,j,1) = (f(i, j-1, 1) || f(i, j-1, 0)) && s2[j] == s3[i+j+1]
    
    要用代码实现格子和顶点，需要将若矩阵扩展成真正的矩阵（一行一插件，行中插空行，一列一隔板，列中插空列），也就可以放弃格子与顶点的差异化表示；
    同时为了实现方便，设置行列分别在头部设置两根哨兵条

    注意边界条件：交织首个字符的情况
    """
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        if not s1:
            return s2 == s3
        elif not s2:
            return s1 == s3
        elif len(s1)+len(s2) != len(s3):
            return False
            
        hi1, hi2 = 2*len(s1)+3, 2*len(s2)+3
        dp = [[False for _ in range(hi2)] for _ in range(hi1)]
        for i in range(2, hi1):
            for j in range(2, hi2):
                if i%2 ^ j%2:
                    if i%2:
                        if i== 3 and j == 2:
                            dp[i][j] = s1[(i-2)//2]==s3[(i+j-5)//2]
                        else:
                            dp[i][j] = (dp[i-1][j-1] or dp[i-2][j]) and s1[(i-2)//2]==s3[(i+j-5)//2]
                    else:
                        if i==2 and j == 3:
                            dp[i][j] = s2[(j-2)//2]==s3[(i+j-5)//2]
                        else:
                            dp[i][j] = (dp[i][j-2] or dp[i-1][j-1]) and s2[(j-2)//2]==s3[(i+j-5)//2]
        
        # for row in dp:
        #     for col in row:
        #         print(int(col), end=',')
        #     print('')
        
        return dp[hi1-2][hi2-1] or dp[hi1-1][hi2-2]


if __name__ == '__main__':
    so = Solution()
    print(so.isInterleave(s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"))
    print(so.isInterleave(s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"))
    print(so.isInterleave(s1 = "", s2 = "", s3 = ""))
    print(so.isInterleave(s1 = "a", s2 = "b", s3 = "a"))
    print(so.isInterleave(s1 = "db", s2 = "b", s3 = "cbb"))
